package cuppics;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import org.junit.Test;

public class Prj33 {

	/**
	 * The fraction 49/98 is a curious fraction, as an inexperienced
	 * mathematician in attempting to simplify it may incorrectly believe that
	 * 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.
	 * 
	 * We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
	 * 
	 * There are exactly four non-trivial examples of this type of fraction,
	 * less than one in value, and containing two digits in the numerator and
	 * denominator.
	 * 
	 * If the product of these four fractions is given in its lowest common
	 * terms, find the value of the denominator.
	 */
	@Test
	public void test() {
		System.out.println(Calculator.calculate());
	}

	public static class Calculator {

		public static int calculate() {

			List<Integer> numerators = new ArrayList<Integer>();
			List<Integer> denominators = new ArrayList<Integer>();

			for (int i = 10; i < 100; i++) {
				for (int j = i + 1; j < 100; j++) {
					if (checkOk(i, j)) {
						numerators.add(i);
						denominators.add(j);
					}
				}
			}

			IntegerDivisor div = new IntegerDivisor();
			Map<Long, Integer> numeratorsMap = new HashMap<Long, Integer>();
			Map<Long, Integer> denominatorsMap = new HashMap<Long, Integer>();

			for (int i = 0; i < numerators.size(); i++) {

				div.divisor(numerators.get(i));
				mergerMap(numeratorsMap, div.primeMap);
				div.clear();

				div.divisor(denominators.get(i));
				mergerMap(denominatorsMap, div.primeMap);
				div.clear();

			}

			for (Entry<Long, Integer> entry : numeratorsMap.entrySet()) {

				Long key = entry.getKey();
				if (denominatorsMap.containsKey(key)) {

					int val = denominatorsMap.get(key)
							- Math.min(numeratorsMap.get(key),
									denominatorsMap.get(key));
					if (val == 0) {
						denominatorsMap.remove(key);
						continue;
					}
					denominatorsMap.put(key, val);
				}
			}

			int sum = 1;
			for (Entry<Long, Integer> entry : denominatorsMap.entrySet()) {
				sum *= Math.pow(entry.getKey(), entry.getValue());
			}
			return sum;

		}

		private static void mergerMap(Map<Long, Integer> numeratorsMap,
				Map<Long, Integer> primeMap) {

			for (Entry<Long, Integer> entry : primeMap.entrySet()) {
				if (!numeratorsMap.containsKey(entry.getKey())) {
					numeratorsMap.put(entry.getKey(), 0);
				}

				numeratorsMap.put(entry.getKey(),
						numeratorsMap.get(entry.getKey()) + entry.getValue());
			}

		}

		private static boolean checkOk(int i, int j) {

			int i1 = i / 10;
			int i2 = i % 10;

			int j1 = j / 10;
			int j2 = j % 10;

			if (j1 != i2) {
				return false;
			}
			return isEqual(i, j, i1, j2);
		}

		private static boolean isEqual(int i, int j, int i1, int j1) {
			return i * j1 == j * i1;
		}
	}

	/**
	 * 因子分解
	 * 
	 * @author 1440
	 * 
	 */
	public static class IntegerDivisor {

		public Map<Long, Integer> primeMap = new HashMap<Long, Integer>();
		public List<Long> primeList = new ArrayList<Long>();

		public void clear() {
			primeMap.clear();
			primeList.clear();
		}

		public void divisor(long num) {

			if (num <= 1)
				return;

			long prime = getPrime(
					num,
					primeList.size() == 0 ? 2
							: primeList.get(primeList.size() - 1));
			if (prime < 0) {
				primeMap.put(num, 1);
				primeList.add(num);
				return;
			} else {

				primeList.add(prime);
				int count = 0;
				do {

					count += 1;
					num = num / prime;
				} while (num % prime == 0);

				primeMap.put(prime, count);

				divisor(num);

			}

		}

		private long getPrime(long num, long start) {

			for (long i = start; i <= Math.sqrt(num); i++) {
				if (num % i == 0) {
					return i;
				}
			}
			return -1;
		}

		@Override
		public String toString() {

			return print_Map(this.primeMap);
		}

		public Long getLargestPrime() {
			return primeList.get(primeList.size() - 1);
		}

	}

	public static String print_Map(Map<?, ?> primeMap) {
		StringBuilder sb = new StringBuilder();
		for (Entry<?, ?> entry : primeMap.entrySet()) {
			sb.append(entry.getKey().toString() + "="
					+ entry.getValue().toString() + "\n");
		}
		return sb.toString();
	}

	public static void print_List(List<Integer> list) {
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i) + ",");
		}
		System.out.println();
	}

}
